package swordoffer.offer8;

public class GetPre {
    public TreeLinkNode getPre(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }
        if(pNode.left != null){
            return getMostRight(pNode.left);
        }else{
            TreeLinkNode parent = pNode.next;
            while(parent != null && parent.left == pNode){
                pNode = parent;
                parent = pNode.next;
            }
            return parent;
        }
    }
    public TreeLinkNode getMostRight(TreeLinkNode node){
        if(node == null){
            return null;
        }
        while(node.right != null){
            node = node.right;
        }
        return node;
    }
}
